1696. Jump Game VI
Medium

You are given a 0-indexed integer array nums and an integer k.

You are initially standing at index 0. In one move, you can jump at most k steps forward without going outside the boundaries of the array. That is, you can jump from index i to any index in the range [i + 1, min(n - 1, i + k)] inclusive.

You want to reach the last index of the array (index n - 1). Your score is the sum of all nums[j] for each index j you visited in the array.

Return the maximum score you can get.

 

Example 1:

Input: nums = [1,-1,-2,4,-7,3], k = 2
Output: 7
Explanation: You can choose your jumps forming the subsequence [1,-1,4,3] (underlined above). The sum is 7.

Example 2:

Input: nums = [10,-5,-2,4,0,3], k = 3
Output: 17
Explanation: You can choose your jumps forming the subsequence [10,4,3] (underlined above). The sum is 17.

Example 3:

Input: nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
Output: 0

 

Constraints:

  •  1 <= nums.length, k <= 105
  • -104 <= nums[i] <= 104
Accepted
13,390
Submissions
34,262
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions
Show Hint 1
Let dp[i] be "the maximum score to reach the end starting at index i". The answer for dp[i] is nums[i] + min{dp[i+j]} for 1 <= j <= k. That gives an O(n*k) solution.
Show Hint 2
Instead of checking every j for every i, keep track of the smallest dp[i] values in a heap and calculate dp[i] from right to left. When the smallest value in the heap is out of bounds of the current index, remove it and keep checking.

Average Rating: 4.08 (25 votes)

Premium

Solution


Overview

You probably can guess from the problem title, this is the sixth problem in the series of Jump Game problems. Those problems are similar, but have considerable differences, making their solutions quite different.

In this problem, for each move, we are allowed to advance k steps, and our target is to maximize the scores we collect.

One example:

Figure 0.1

Below, five approaches are introduced.

Generally, we recommend Approach 1: Dynamic Programming + Deque and Approach 4: Dynamic Programming + Deque (Compressed) since they have the best performance.

Also, because it is a medium level problem, we allow some relevant slower approaches: Approach 2: Dynamic Programming + Priority Queue and Approach 3: Segment Tree.

Note that Approach 4: Dynamic Programming + Deque (Compressed) and Approach 5: Dynamic Programming + Priority Queue (Compressed) are the state compressed version of Approach 1 and Approach 2.


Approach 1: Dynamic Programming + Deque

Intuition

Note: This approach is a little bit beyond the medium level question, so if you are struggling to understand this, you should at least finish the DP part, and then feel free to jump to Approach 2 , which is easier but has a slower performance.

However, it is still strongly recommended to understand this whole approach since it is not that hard.

In this part, we will explain how to think of this approach step by step.

If you are only interested in the pure algorithm, you can jump to the algorithm part.

For the Jump Game series questions, dynamic programming is our old friend. It's natural to try DP first.

To implement DP, we need a dp array. What should the DP array represent?

Since the problem ask us the max score we can get ending at the last index, how about letting dp[i] represent the max score we can get ending at index i?

Also, you can let dp[i] represent the max score we can get starting at index i. That is similar.

To have better naming, we rename dp to score. So, score[i] represents the max score we can get ending at index i.

For example:

Figure 1.1

OK. Let's dive deeper.

For a DP solution, basically, we need two things:

  1. The base case.

This is where our dp start. Usually, this means how to calculate dp[0]. In our case, score[0] = nums[0] since nums[0] is both our start and end. We only have one choice.

  1. The so-called transition equation.

That is to say, if we have already calculated score[0], score[1], ..., score[i-1], how can we calculate score[i]?

Since we can only advance k steps, to arrive nums[i], we must jump from one of nums[i-k], nums[i-k+1], ..., nums[i-1]. We only need to pick the one with maximum score.

For example, if we are calculating score[3] and k=3, we need to decide jump from index 0, 1, or 2:

Figure 1.2

OK, now we have a transition equation:

score[i] = max(score[i-k], ..., score[i-1]) + nums[i]

However, this equation needs O(k)\mathcal{O}(k) to calculate score[i], which makes the overall complexity come to O(Nk)=109\mathcal{O}(Nk) = 10^{9} in the worst case, given that NN is the length of nums.

This complexity is too much and we need to improve it.

Somehow, this equation is similar to Sliding Window Maximum, which is a typical monotonic queue problem. We can use the same technique to make some improvements.

Note that when calculating maximum, we do not need all score[i-k], ..., score[i-1]; we just need some large values.

For example, if k == 3 and [score[i-3], score[i-2], score[i-1]] = [2, 4, 10], their maximum is score[i-1] = 10. In this case, when calculating following score[i] (and further score[i+1]), we do not need score[i-3] = 2 and score[i-2] = 4, since they are smaller than score[i-1] = 10.

The picture illustrates another example when calculating score[2]:

Figure 1.3

In this case, we maintain a deque as a monotonically decreasing queue. Since it is monotonically decreasing, the maximum value is always at the top of the queue.

In practice, since we store scores in score, we only need to store the index in the queue.

Also, remember to pop the index smaller than i-k out of the queue from the left.

Algorithm

Step 1: Initialize a dp array score, where score[i] represents the max score starting at nums[0] and ending at nums[i].

Step 2: Initialize a deque array dq storing indexes of nums such that the corresponding values are monotonically decreasing.

Step 3: Iterate over nums. For each element nums[i]:

  • Pop all the indexes smaller than i-k out of dq from left.
  • Update score[i] to score[dq.peekFirst()] + nums[i].
  • If the corresponding score of the rightmost index in dq (i.e., score[dq.peekLast()]) is smaller than score[i], pop it from the right to make corresponding values monotonically decreasing. Repeat.
  • Push i into the right of dq.

Step 4: Return the last element of score.

Challenge: Can you implement the code yourself without seeing our implementations?

Implementation

Complexity Analysis

Let NN be the length of nums.

  • Time Complexity: O(N)\mathcal{O}(N), since we need to iterate nums, and push and pop each element into the deque at most once.

  • Space Complexity: O(N)\mathcal{O}(N), since we need O(N)\mathcal{O}(N) space to store our dp array and O(k)\mathcal{O}(k) to store dq.


Approach 2: Dynamic Programming + Priority Queue

Intuition

In Approach 1, we got the following transition equation for Dynamic Programming:

score[i] = max(score[i-k], ..., score[i-1]) + nums[i]

If you are not familiar with the monotonic queue technique mentioned in Approach 1, and still want to find out the maximum quickly, Priority Queue (Heap) is for you. Heap maintain and return the max value in log\log time.

Figure 2.1

If we found that the index of the maximum score is less than i-k, just pop out and get the next maximum score.

Algorithm

Step 1: Initialize a dp array score, where score[i] represents the max score starting at nums[0] and ending at nums[i].

Step 2: Initialize a max-heap priority_queue.

Step 3: Iterate over nums. For each element nums[i]:

  • If the index of top of priority_queue is less than i-k, pop the top. Repeat.
  • Update score[i] to the sum of corresponding score of the index of top of priority_queue and nums[i] (i.e., score[priorityQueue.peek()[1]] + nums[i]).
  • Push pair (score[i], i) into priority_queue.

Step 4: Return the last element of score.

Challenge: Can you implement the code yourself without seeing our implementations?

Implementation

Complexity Analysis

Let NN be the length of nums.

  • Time Complexity: O(NlogN)\mathcal{O}(N \log N), since we need to iterate nums, and push and pop each element into the deque at most once, and for each push and pop, it costs O(logN)\mathcal{O}(\log N) in the worst case.

  • Space Complexity: O(N)\mathcal{O}(N), since we need O(N)\mathcal{O}(N) space to store our dp array and O(N)\mathcal{O}(N) to store priority_queue.


Approach 3: Segment Tree

Intuition

In Approach 1, we got the following transition equation for Dynamic Programming:

score[i] = max(score[i-k], ..., score[i-1]) + nums[i]

There is also another way to find out the interval maximum in log\log time: Segment Tree.

Since we already have some great explanations on Segment Tree, here we will not provide a detailed explanation of implementation. You can find some comprehensive tutorials on Recursive Approach to Segment Trees or Range Sum Query - Mutable.

Now, we will have a quick review of the segment tree and then explain how we can use it to tackle our problem.

As we know, the segment tree is a data structure used for storing information about intervals. Given that NN is the size of the tree, this data structure allows us to query and to update the information about a certain interval in O(log(N))\mathcal{O}(\log(N)) time.

Take the segment tree for querying interval max for an example:

Figure 3.1

Usually, we store the tree in an array. We need twice the size of the original array to store the segment tree.

Here, we leave the index 0 unused for the convenience of indexing. You can also choose to use it by shifting the whole tree to left by one unit. In our approach, the left and right children of node i are 2*i and 2*i + 1 respectively.

Given that n is the size of the original array, from the node n to node 2*n - 1, we store the original array itself. For other nodes, we store the value of node i as the sum of node 2*i and node 2*i + 1.

The segment tree allows us to query the max of a certain interval and to update the values of elements. It should be able to process both actions in O(log(N))\mathcal{O}(\log(N)) time. Let's see some examples.

Updating Value

For update, what we do is simple. Just update the value from the leaf to the root. For instance:

Figure 3.2

Querying Sum

For query, the case is a bit complicated. Generally speaking, we are dividing the target interval into a few pre-calculated segments to reduced run time. For example:

Figure 3.3

OK. Now back to our problem. How can we use the segment tree?

For each element nums[i], we need to query max(score[i-k], ..., score[i-1]), and then update the value of index i in Segment Tree to that maximum plus nums[i]. Both actions can be implemented in log\log time.

Algorithm

Step 1: Implement the Segment Tree. Since the tree is initialized to all zeros, only update and query need to be implemented.

Step 2: Iterate over nums. For each element nums[i]:

  • query the maximum from index i-k to index i.
  • update value of index i to that maximum plus nums[i].

Step 3: Return the last element of the segment tree.

Challenge: Can you implement the code yourself without seeing our implementations?

Implementation

Complexity Analysis

Let NN be the length of nums.

  • Time Complexity: O(NlogN)\mathcal{O}(N \log N), since we need to iterate nums, and for each element we need to perform the query and update once, which costs O(logN)\mathcal{O}(\log N) in the worst case.

  • Space Complexity: O(N)\mathcal{O}(N), since we need O(N)\mathcal{O}(N) space to store our segment tree.


Approach 4: Dynamic Programming + Deque (Compressed)

Intuition

Note that in Approach 1, when calculating score[i], we do not need all values from score[0] to score[i-1]; we only need part of values from score[i-k] to score[i-1]. We can drop the previous values to save memory.

But how? Note that we have a deque array dq, we can save score[i] when saving index i, and drop the whole score array. That is to say, we save a pair (i, score[i]) in the deque. The length of dq is at most O(k)\mathcal{O}(k), so the space complexity is down to O(k)\mathcal{O}(k).

Algorithm

Step 1: Initialize an integer score.

Step 2: Initialize a deque array dq.

Step 3: Iterate over nums. For each element nums[i]:

  • Pop all the indexes smaller than i-k out of dq from left.
  • Update score to dq.peekFirst()[1] + nums[i].
  • If the corresponding score of the rightmost index in dq (i.e., dq.peekLast()[1]) is smaller than score, pop it from the right to make corresponding values monotonically decreasing. Repeat.
  • Push (i, score) into the right of dq.

Step 4: Return score.

Challenge: Can you implement the code yourself without seeing our implementations?

Implementation

Complexity Analysis

Let NN be the length of nums.

  • Time Complexity: O(N)\mathcal{O}(N), since we need to iterate nums, and push and pop each element into the deque at most once.

  • Space Complexity: O(k)\mathcal{O}(k), since we need O(k)\mathcal{O}(k) to store dq.


Approach 5: Dynamic Programming + Priority Queue (Compressed)

Intuition

Similar to Approach 4, when calculating score[i], we do not need all values from score[0] to score[i-1]; we only need values from score[i-k] to score[i-1]. We can drop the previous values to save memory.

Since we already save the (score[i], i) pair in our Priority Queue, we can directly drop the score array.

However, the length of our Priority Queue is O(N)\mathcal{O}(N) in the worst case, given that NN is the length of nums. That is to say, we can not decrease the big-O space complexity. Nevertheless, we still decrease memory usage by half by dropping the score array.

Algorithm

Step 1: Initialize an integer score.

Step 2: Initialize a max-heap priority_queue.

Step 3: Iterate over nums. For each element nums[i]:

  • If the index of top of priority_queue is less than i-k, pop the top. Repeat.
  • Update score to the sum of corresponding score of the index of top of priority_queue and nums[i] (i.e., priorityQueue.peek()[0] + nums[i]).
  • Push pair (score, i) into priority_queue.

Step 4: Return score.

Challenge: Can you implement the code yourself without seeing our implementations?

Implementation

Complexity Analysis

Let NN be the length of nums.

  • Time Complexity: O(NlogN)\mathcal{O}(N \log N), since we need to iterate nums, and push and pop each element into the deque at most once, and for each push and pop, it costs O(logN)\mathcal{O}(\log N) in the worst case.

  • Space Complexity: O(N)\mathcal{O}(N), since we need O(N)\mathcal{O}(N) to store priority_queue.

Report Article Issue

Comments: 11
Dirk41's avatar
Read More

This should be a hard level question

27
Show 4 replies
Reply
Share
Report
tupac_shakur's avatar
Read More

Thanks for the detailed explanation 🙂

8
Reply
Share
Report
thedeg123's avatar
Read More

This seems a hard questions as the priority queue step in answer 2 can be used to solve sliding window maximum (a LC hard question).

5
Reply
Share
Report
yhossam95's avatar
Read More

This problem is kind of an extension to the max sliding window problem, which is labelled as a hard, so this one definitely deserves a hard.

1
Reply
Share
Report
_noexcuses's avatar
Read More

Good problem and good explanation! One thing though: It's not guaranteed that k is always less than the length of nums so getting rid of score array will not necessarily improve the space complexity.

1
Reply
Share
Report
MaidaWu's avatar
Read More

Great explanation!

1
Reply
Share
Report
h1aihan's avatar
Read More

My brain stopped after I came up with a O(n^2) dp solution and then it exceeds time limit, and I am not able to get my brain to restart to comprehend these sliding window and priority queue methods after I looked at the solution, sad.

0
Reply
Share
Report
kylinzhuo's avatar
Read More

C++ Solution 1: line 11 while loop can also be a for loop.

if (!dq.empty() && dq.front() < i-k) {

0
Reply
Share
Report
Kool_head's avatar
Read More

Thanks for the solution.

Another simple Sliding window solution with O(1) space & O(n) runtime
https://leetcode.com/problems/jump-game-vi/discuss/981340/Explained%3A-Simple-Sliding-window-solution-with-O(1)-space-and-O(n)-runtime

0
Reply
Share
Report
shukria's avatar
Read More

Thanks for nice explanation, leetcode articles getting better and better now a days. Need one clarification on Approach 5 Time Complexity. How is time complexity O(NlogN)? I thought priorityQueue.remove();itself would be O(N).

0
Show 1 reply
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.